package solution;

import java.util.*;

/**
 * BreadthFirstPaths.java
 * @param <V>
 * ------------------------------------------------------------------------
 * The s-t connectivity problem.
 * - Given source vertex s and a target vertex t, is there a path between s and t?
 */
public class BreadthFirstPaths<V> {
    private V s;

    private Set<V> marked;

    private Map<V, V> edgeTo;

    private Map<V, Integer> distance;

    public BreadthFirstPaths(Graph<V> graph, V s) {
        this.s = s;
        this.marked = new HashSet<>();
        this.edgeTo = new HashMap<>();
        this.distance = new HashMap<>();

        bfs(graph, s);
    }

    private void bfs(Graph<V> graph, V v) {
        marked.add(v);
        Queue<V> queue = new LinkedList<>();
        queue.add(v);
        distance.put(v, 0);
        while (!queue.isEmpty()) {
            V current = queue.remove();

            for (Edge<V> edge : graph.neighbors(current)) {
                V w = edge.getTo();
                if (!marked.contains(w)) {
                    marked.add(w);
                    edgeTo.put(w, current);
                    distance.put(w, distance.get(current) + 1);
                    queue.add(w);
                }
            }


        }
    }

    public boolean hasPathTo(V v){
        return marked.contains(v);
    }

    public Iterable<V> pathTo(V v){
        if (!hasPathTo(v)) {
            return null;
        }
        List<V> path = new ArrayList<>();

        for (V x = v; x != s; x = edgeTo.get(x)) {
            path.add(x);
        }

        path.add(s);

        Collections.reverse(path);
        return path;
    }


}
